Sums of the form

can be evaluated in $O(\log n)$ time. See Summation of Floor Function Series for a special case.

Problems

• It's a Mod, Mod, Mod, Mod World

External links

• Summation of Floor Function Series
• Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, Chapter 3.5, Floor/Ceiling Sums.